#include<stdio.h>
#include<string.h>
#include<stdlib.h>


// *****************单向链表**********************
//*
//*

//节点结构体
struct LinkNode{
    //数据域
    void * data;
    // 指针域
    struct LinkNode *next;
};


//链表结构体
struct LList{
     //头节点
     struct LinkNode  pHeader;
     // 链表长度
     int m_Size;    
};

typedef void * LinkList;

// 初始化链表
LinkList init_LinkList(){
    struct LList * myList =  malloc(sizeof(struct LList));
    if(myList == NULL){
        return NULL;
    } 

    myList->pHeader.data = NULL;
    myList->pHeader.next = NULL;
    myList->m_Size = 0;
    return myList;
}

//插入链表
void insert_LinkList(LinkList list, int pos, void *data){
    if(NULL == list){
        return;
    }

    if(NULL == data){
        return;
    }

    // 将list 还原成struct LList 数据类型
    struct LList * myList = list;
    if(pos<0 || pos>myList->m_Size){
        // 无效的位置强制做尾插
        pos = myList->m_Size;
    }

    // 找到插入节点的前驱节点位置
    struct LinkNode * pCurrent = &(myList->pHeader);   // 注意，取地址
    for(int i=0;i<pos;i++){
        pCurrent = pCurrent->next;
    }

    // 创建新节点
    struct LinkNode * newNode = malloc(sizeof(struct LinkNode));
    newNode->data = data;
    newNode->next = NULL;

    // 建立节点关系
    newNode->next= pCurrent->next;
    pCurrent->next = newNode;

    // 跟新节点长度
    myList->m_Size++;

}


//遍历链表
void foreach_LinkList(LinkList list, void(*myForeach)(void *)){
    if(NULL == list){
        return;
    }

    struct LList * mylist = list;
    struct LinkNode * PCurrent = mylist->pHeader.next;
    for(int i=0;i<mylist->m_Size;i++){
        //打印
        myForeach(PCurrent->data);
        PCurrent = PCurrent->next;
    }
}

//删除链表 按位置
void removeByPos_LinkList(LinkList list, int pos){
    if(NULL == list){
        return;
    }
    struct LList * mylist = list;
    if(pos<0 || pos > mylist->m_Size-1){
        return;
    }

    // 找到待删除节点的前驱节点
    struct LinkNode * pCurrent = &mylist->pHeader;
    for(int i=0;i<pos;i++){
        pCurrent = pCurrent->next;
    }
    
    // 记录待删除的节点
    struct LinkNode * pDel = pCurrent->next;

    // 重新建立节点关系
    pCurrent->next = pDel->next;
    free(pDel);
    pDel = NULL;

    // 更新链表的长度
    mylist->m_Size--;
    
    
}

// 按值删除
void removeByValue_LinkList(LinkList list, void * data, void(* myCompare)(void *,void *)){
    if(NULL==list){
        return;
    }
    if(NULL==data){
        return;
    }

    struct LList * mylist = list;
    // 创建两个辅助指针
    struct LinkNode * pPrev = &mylist->pHeader;
    struct LinkNode * pCurrent = pPrev->next;

    for(int i=0;i<mylist->m_Size;i++){
        //pCurrent->data  data 将两个指针比较利用回调 交给用户
        if(compare(pCurrent->data, data)){
            pPrev->next = pCurrent->next;
            free(pCurrent);
            mylist->m_Size--;
            break;
        }
        pPrev=pCurrent;
        pCurrent = pCurrent->next;
    }
}

// 清空链表
void clear_LinkList(LinkList list){
    if(list == NULL){
        return
    }

    struct LList * mylist = list;

    struct LinkNode * pCurrent = mylist->pHeader.next;
    for(int i=0;i<mylist->m_Size;i++){
        struct LinkNode * pNext = pCurrent->next;
        free(pCurrent);
        pCurrent = pNext;
    }
    
    mylist->pHeader.next = NULL;
    mylist->m_Size = 0;
}

// 返回链表的长度
int size_LinkList(Linklist list){
    if(list == NULL){
        return -1;
    }

    struct LList * mylist = list;
    return mylist->m_Size;
}

// 销毁链表
void destroy_linklist(LinkList list){
    if(list == NULL){
        return;
    }

    //清空
    clear_LinkList(list);
    free(list);
    list=NULL;
}



//**************************************测试****************************************

struct Person{
    char name[64];
    int age;
};

// 用户自定义遍历
void myForeach(void * data){
     struct Person * p = data;
     printf("姓名:%s  年龄:%d \n", p->name, p->age);
}

// 用户自定义比较
int myCompare(void * data1,void * data2){
    struct Person * p1 = data1;
    struct Person * p2 = data2;

    return strcmp(p1->name,p2->name) == 0 && p1->age == p2->age;
}


void test1(){
    struct Person p1 = {"牛牛", 18};
    struct Person p2 = {"花花", 20};
    struct Person p3 = {"珍珍", 18};
    struct Person p4 = {"莲莲", 15};
    struct Person p5 = {"爱爱", 18};
    struct Person p6 = {"然然", 30};

    // 初始化链表
    LinkList mylist = init_LinkList();

    // 插入数据
    insert_LinkList(mylist, -1, &p1);
    insert_LinkList(mylist, 0, &p2);
    insert_LinkList(mylist, 3, &p3);
    insert_LinkList(mylist, -1, &p4);
    insert_LinkList(mylist, 2, &p5);
    insert_LinkList(mylist, 0, &p6);

    foreach_LinkList(mylist,myForeach);

    // 删除
    removeByPos_LinkList(mylist, 4);
    printf("***************删除*********\n");
    foreach_LinkList(mylist,myForeach);


}





int main(){


    test1();


    return 0;
}


